# -*- coding:utf-8 -*-
"""
@Time:  2024/6/15 15:52
@Auth:  Mrs.Gou 
@Function:快排
"""

height = [155, 187, 172, 160, 163, 166, 173, 182, 165, 159]


def q_sort(height: list, left: int, right: int):
    """
    分析
    :param height: 因为传地址
    :param left: 因为递归的时候，需要知道左边和右边
    :param right:
    :return:
    """

    # 找元素的两个指针
    l, h = left, right
    # 选取最右边的一个为基准
    base = height[h]

    while l < h:
        while l < h:
            # 从左往右找比基准大的，交换到h位置
            if height[l] > base:
                height[l], height[h] = height[h], height[l]
                h -= 1
                # 找到后停止，要交换方向
                break
            else:
                # 如果没找到，继续找
                l += 1

        while l < h:
            # 再从h位置从右往左找比基准小的，交换到之前l的位置
            if height[h] < base:
                height[l], height[h] = height[h], height[l]
                l += 1
                # 找到后停止，要交换方向
                break
            else:
                # 如果没找到，继续找
                h -= 1
    # 左边至少还有两个元素，才递归
    if l - left > 1:
        q_sort(height, left, l - 1)
    # 右边至少还有两个元素，才递归
    if right - h > 1:
        q_sort(height, h + 1, right)


# 下标是长度-1
q_sort(height, 0, len(height) - 1)
print(height)
